package week02

import "fmt"

// 706. 设计哈希映射
// https://leetcode-cn.com/problems/design-hashmap/

const slotCount = 100

type Node struct {
	key int
	val int
	pre *Node
	next *Node
}

type List struct {
	head *Node
}

func (list *List) insert(key, val int) {
	if node := list.find(key); node != nil {
		node.val = val
		return
	}
	node := &Node{
		key: key,
		val: val,
	}
	headNext := list.head.next
	if headNext != nil {
		headNext.pre = node
	}
	node.next = headNext
	node.pre = list.head
	list.head.next = node
}

func (list *List) find(key int) *Node {
	node := list.head.next
	for node != nil {
		if node.key == key {
			return node
		}
		node = node.next
	}
	return nil
}

func (list *List) remove(key int) {
	if node := list.find(key); node != nil {
		node.pre.next = node.next
		if node.next != nil {
			node.next.pre = node.pre
		}
	}
}

func (list *List) print() {
	node := list.head.next
	for node != nil {
		fmt.Println(fmt.Sprintf("node.val: %d", node.val))
		node = node.next
	}
}

func NewList() *List {
	return &List {
		head: &Node{},
	}
}


type MyHashMap struct {
	slot [slotCount]*List
}


/** Initialize your data structure here. */
func Constructor() MyHashMap {
	var slot [slotCount]*List
	for i := range slot {
		slot[i] = NewList()
	}

	return MyHashMap {
		slot: slot,
	}
}


/** value will always be non-negative. */
func (this *MyHashMap) Put(key int, value int)  {
	this.slot[this.hash(key)].insert(key, value)
}


/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
func (this *MyHashMap) Get(key int) int {
	if node := this.slot[this.hash(key)].find(key); node != nil {
		return node.val
	}
	return -1
}


/** Removes the mapping of the specified value key if this map contains a mapping for the key */
func (this *MyHashMap) Remove(key int)  {
	this.slot[this.hash(key)].remove(key)
}

func (this *MyHashMap) hash(key int) int {
	return key % slotCount
}
